1. Field of the Invention
This invention relates to cryptographic systems (cryptosystems) for data and information protection, and in particular to public-key cryptosystems for data and information protection in communications, to their related methods and protocols.
2. Background Description
Advances in computer and digital technology have been expanding the scope of business applications at a fast pace. Information in electronic or digital form is being used to an ever greater extent and is replacing older methods of information management, resulting in a rapid increase in the volume of digital data stored, retrieved, shared, transmitted and exchanged. Yet all applications are faced with the challenge of protecting data and information on one level or another against unauthorized access and deliberate tampering. The challenge is more prominent when data need to be transferred from one physical location to another over some communications channels that are not secure or, in most cases, the physical media used for these communications, such as a radio link, make it infeasible or impossible to guarantee exclusive access. Financial transactions like those between banks, private information such as electronic mail, proprietary or confidential data such as mobile phone identifications or pins used in electronic banking, are all examples of applications where data and information protection is indispensable. In general, for a great many applications, data need to be protected while being physically moved from one location to another or while being statically or transiently stored on hard disks, tapes, in memory, or other media.
Three primary attributes of modern information management and communications are: security, authenticity and data integrity. Cryptography is a means to construct information and communication systems having these attributes.
Protection of data/information by ways of scrambling using unpublished methods and secret encryption has a fairly long history. But public-key cryptography was only recently pioneered by W. Diffie and M. Hellman with their milestone paper "New Directions in Cryptography", IEEE Transactions on Information Theory, Vol. IT-22, 1976, pp. 644-654. The first scheme of secure communications over insecure media, introduced by Diffie and Hellman, is described in U.S. Pat. No. 4,200,770. In such a scheme, a key is securely exchanged and established between two communicating parties totally without any pre-arrangement for such a key, although the realization of the scheme is not a public-key cryptosystem and, for this basic key exchange scheme, the same key may not be later exchanged with another third party.
The first true public-key cryptosystem, a knapsack cryptosystem, was proposed by R. Merkle and M. Hellman (see "Hiding Information and Signatures in Trapdoor Knapsacks", IEEE Transactions on Information Theory, Vol. IT-24, 1978, pp. 525-530, and also see U.S. Pat. No. 4,218,582). The system offers public-key encryption and a scheme for digital signature. However, a few years after the issuance of the patent, it was shown to be insecure.
Since the concept of one-way trapdoor and asymmetricity in cryptography was introduced, many public-key cryptosystems have been invented. The RSA cryptosystem is described in U.S. Pat. No. 4,405,829 to Rivest, Shamir and Adleman. The cryptosystem of T. ElGamal is depicted in "A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms", IEEE Transactions on Information Theory, Vol. 31, 1985, pp. 469-472. The recently advanced cryptographic systems using elliptic curves started with Victor S. Miller's paper "Use of Elliptic Curves in Cryptography", Advances in Cryptology CRYPTO '85 Proceedings, Berlin: Springer-Verlag, 1985, pp. 417-426. As an example, see the scheme of U. Maurer, U.S. Pat. No. 5,146,500.
The public-key cryptographic methods of today are based on three types of mathematical hard problems: discrete logarithm, factorization of composite of large primes, and knapsack. Some are based on the variations of the three basic problems, such as error correcting codes and product of finite automata. Knapsack cryptosystems, with the exception of Chor-Rivest cryptosystem, are the only ones that can achieve practical data encryption/decryption speed with current technology for application needs in general. The other types all suffer from low speed for encryption, decryption and/or key generation. As a result, efforts in developing knapsack cryptosystems have been tremendous, prolific and, despite repeated very disappointing revelation of weakness in their security, persistent. Nevertheless, the outlook of knapsack cryptosystems has not been encouraging. Besides a common imperfection of such cryptosystems, namely data expansion during encryption that results in a low information rate, the great majority of knapsack cryptosystems have been broken since 1982 with the first valid attack by Shamir on the basic Merkle-Hellman cryptosystem (see "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem", Advances in Cryptology: Proceedings of CRYPTO '82, Plenum Press, 1983, pp. 279-288), the successful cryptanalysis by Brickell of the multiple iterated version (see "Breaking Iterated Knapsacks", Advances in Cryptology, Proceedings of CRYPTO '84, Berlin: Springer-Verlag, 1985, pp. 342-358), and the implementation of the L.sup.3 (Lenstra, Lenstra and Lovacz) lattice basis reduction algorithm which is powerful and applies in general to knapsack problems, not just knapsack cryptosystems.
S. C. Lu and L. N. Lee proposed a more generalized version of knapsack cryptosystem using the Chinese Remainder Theorem (see "A Simple and Effective Public-Key Cryptosystem", COMSAT Technical Review, Vol. 9, No. 1, 1979, pp. 15-24). R. M. Goodman and A. J. McAuley developed another variant of knapsack cryptosystem (see "New Trapdoor Knapsack Public Key Cryptosystem", Advances in Cryptology: Proceedings of EUROCRYPT '84, Berlin: Springer-Verlag, 1985, pp. 150-158). H. Isselhorst advanced a knapsack cryptosystem using rational number (see "The Use of Fractions in Public-Key Cryptosystems", Advance in Cryptology EUROCRYPT '89, Berlin: Springer-Verlag, 1990, pp. 47-55). V. Niemi also proposed a knapsack cryptosystem (see "A New Trapdoor in Knapsacks", Advances in Cryptology EUROCRYPT '91 Proceedings, Berlin: Springer-Verlag, 1991, pp. 405-411). Another fast cryptosystem was by R. J. McEliece based on error correcting Goppa codes (see JPL (Jet Propulsion Laboratory) DSN (Deep Space Network) Progress Report 42-44, January-February 1978, pp. 114-116). All these cryptographic schemes and systems as well as various other knapsack variations were cryptanalized and described in the following papers: "A survey of recent results" by Brickell and Odlysko, Contemporary Cryptology, IEEE Press, 1992, pp. 501-540; "Cryptanalysis of Public-Key Cryptosystem based on Approximations by Rational Numbers" by J. Stern and P. Toffin, Advances in Cryptology EUROCRYPT '91, Berlin: Springer-Verlag, 1991, pp. 313-317; "The Cryptanalysis of a New Public-Key Cryptosystem based on Modular Knapsacks", by Y. M. Chee, A. Joux and J. Stern in Advances in Cryptology CRYPTO '91, Berlin: Springer-Verlag, 1991, pp. 204-212; "Cryptanalysis of McEliece's Public-Key Cryptosystem" by A. I. Turkin, Advances in Cryptology EUROCRYPT '91, Berlin: Springer-Verlag, 1991, pp. 68-70. Several knapsack type cryptosystems are not known to be broken or completely broken: the linearly shift knapsack cryptosystem by C. S. Laih et al (see "Linearly Shift Knapsack Public-Key Cryptosystem", IEEE Journal Selected Areas in Communication, Vol. 7, No. 4, May 1989, pp. 534-539), the Chor-Rivest cryptosystem (see "A Knapsack Type Public-Key Cryptosystem based on Arithmetic in Finite Fields", Advances in Cryptology CRYPTO '84, Berlin: Springer-Verlag, 1985, pp. 54-65), and the residue knapsack cryptosystem of Glen A. Orton (see "A Multiple-Iterated Trapdoor for Dense Compact Knapsacks", Advances in Cryptology CRYPTO '94, Berlin: Springer-Verlag, 1994, pp. 112-130, and U.S. Pat. No. 5,297,206). However, since partial exposure is not adequately addressed, these systems face potential threat. As mentioned earlier, the L.sup.3 lattice basis reduction algorithm is powerful and there have been improvements in applying it, such as the results published by C. P. Schnorr and H. H. Horner in "Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction", Advances in Cryptology EUROCRYPT '95 Proceedings, Berlin: Springer-Verlag, 1995, pp. 1-12.
The quality of a cryptosystem depends on its security, performance, flexibility, cost and scope of applications. Such dependent factors are inter-related and, in a lot of cases, the improvement of one may result in the degradation of another or others.
In the prior art, cryptosystems can be classified into two major categories, the classic, private-key or symmetric cryptosystems, such as DES, and public-key or asymmetric cryptosystems, such as RSA. Public-key cryptosystems can be further categorized into single-layer and multi-layer cryptosystems.
When a public-key cryptosystem uses more than one layer, (i.e. when it encrypts the keys that are used to perform encryption), it is a multi-layer cryptosystem. Such a system is more complex than a single-layer cryptosystem, and key establishment requires additional time. The use of multi-layers in the prior art cryptosystems is mostly due to the slow speed of the cryptographic method, such as RSA, that provides the asymmetricity and the security needed. However, in the prior art, few cryptosystems are reported to use more than two layers and layers are not used for increased security in asymmetricity.
Since the late 1970's, quite a number of public-key cryptosystems have been proposed. Of all that are proposed so far, many have more theoretical interest than practicality and among them only a handful resisted attacks and remain unbroken. Some that have promised practicality are Chor-Rivest Knapsack Cryptosystem, Cryptosystems based on Discrete Exponentiation, McEliece Cryptosystem, Elliptic Curves Cryptosystems, and--the best known--RSA Cryptosystem.
However, improvements and new approaches to existing cryptographic methods and apparatuses are needed to provide secure cryptosystems that offer high level performance and robustness.